#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/7/19 10:36|10:36
# @Author  : yangdingyi
# @File    : 2020-07-19.2.5465.子树中标签相同的节点数
# @Software: PyCharm
from typing import List


class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        ans = [0 for i in range(n)]
        mm = [[] for i in range(n)]
        for e in edges:
            mm[e[0]].append(e[1])
            mm[e[1]].append(e[0])
        ss = [0 for i in range(n)]

        def search(x, dep=0):
            ret = [0 for i in range(26)]
            ret[ord(labels[x])-ord('a')] = 1
            ss[x] = 1
            for y in mm[x]:
                if ss[y] == 1:
                    continue
                retx = search(y, dep+1)
                for i in range(26):
                    ret[i] += retx[i]
            ans[x] = ret[ord(labels[x])-ord('a')]
            return ret

        cc = search(0)
        # for i in range(n):
        #     ans[i] = cc[ord(labels[i])-ord('a')]

        return ans


solve = Solution()

questions = [
    (7, [[0, 1], [0, 2], [1, 4], [1, 5], [2, 3], [2, 6]], "abaedcd"),
    (4, [[0, 1], [1, 2], [0, 3]], "bbbb"),
    (5, [[0, 1], [0, 2], [1, 3], [0, 4]], "aabab"),
    (6, [[0, 1], [0, 2], [1, 3], [3, 4], [4, 5]], "cbabaa"),
    (7, [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]], "aaabaaa"),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print(solve.countSubTrees(q[0], q[1], q[2]))

